package top.kiterunner.learning.moon_test;

/**
 * AdorynZhao in Tencent-UESTC.
 * Source Code Created on 2017/7/13.
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] num = {2,6,1,4,0,8};

        sort(num, 0, num.length-1);

        for(int i : num)
            System.out.print(i + " ");
    }

    public static void sort(int[] num, int start, int end) {
        if(num == null || num.length == 0)
            return;

        if( start >= end)
            return;

        int mid = start + (end - start)/2;
        sort(num,  start, mid);
        sort(num, mid+1, end);
        merge(num, start, mid, end);
    }

    public static void merge(int[] num, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        int[] tmp = new int[num.length];

        for (int k = lo; k <= hi; k++)
            tmp[k] = num[k];

        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                num[k] = tmp[j++];
            else if (j > hi)
                num[k] = tmp[i++];
            else if (tmp[j] < tmp[i])
                num[k] = tmp[j++];
            else
                num[k] = tmp[i++];
        }
    }
}
